#include <vector>
using namespace std;

/*
面试题 17.23. 最大黑方阵
已解答
中等
相关标签
相关企业
提示
给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。

示例 1：

输入：
[
   [1,0,1],
   [0,0,1],
   [0,0,1]
]
输出：[1,0,2]
解释：输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
示例 2：

输入：
[
   [0,1,1],
   [1,0,1],
   [1,1,0]
]
输出：[0,0,1]
提示：

matrix.length == matrix[0].length <= 200
*/

// 法一
class Solution {
public:
    vector<int> findSquare(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (n == 0) return {};

        vector<vector<int>> right(n, vector<int>(n, 0));
        vector<vector<int>> down(n, vector<int>(n, 0));

        // 预处理right数组
        for (int i = 0; i < n; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                if (matrix[i][j] == 0) {
                    right[i][j] = 1;
                    if (j + 1 < n) {
                        right[i][j] += right[i][j + 1];
                    }
                } else {
                    right[i][j] = 0;
                }
            }
        }

        // 预处理down数组
        for (int j = 0; j < n; ++j) {
            for (int i = n - 1; i >= 0; --i) {
                if (matrix[i][j] == 0) {
                    down[i][j] = 1;
                    if (i + 1 < n) {
                        down[i][j] += down[i + 1][j];
                    }
                } else {
                    down[i][j] = 0;
                }
            }
        }

        // 遍历所有可能的k，从大到小
        for (int k = n; k >= 1; --k) {
            for (int r = 0; r <= n - k; ++r) {
                for (int c = 0; c <= n - k; ++c) {
                    if (right[r][c] >= k && 
                        down[r][c + k - 1] >= k && 
                        right[r + k - 1][c] >= k && 
                        down[r][c] >= k) {
                        return {r, c, k};
                    }
                }
            }
        }

        return {};
    }
};

// 法二
class Solution {
	public:
	vector<int> findSquare(vector<vector<int>>& matrix) {
		int n = matrix.size();
		if (n == 0) return {};
		
		// 预处理向右和下方向连续0的数目
		vector<vector<int>> right(n, vector<int>(n, 0));
		vector<vector<int>> down(n, vector<int>(n, 0));
		
		for (int r = 0; r < n; ++r) {
			for (int c = n - 1; c >= 0; --c) {
				if (matrix[r][c] == 0) {
					right[r][c] = (c + 1 < n) ? right[r][c + 1] + 1 : 1;
				} else {
					right[r][c] = 0;
				}
			}
		}
		
		for (int c = 0; c < n; ++c) {
			for (int r = n - 1; r >= 0; --r) {
				if (matrix[r][c] == 0) {
					down[r][c] = (r + 1 < n) ? down[r + 1][c] + 1 : 1;
				} else {
					down[r][c] = 0;
				}
			}
		}
		
		int max_size = 0;
		int res_r = -1, res_c = -1;
		
		for (int r = 0; r < n; ++r) {
			for (int c = 0; c < n; ++c) {
				if (matrix[r][c] != 0) continue;
				int max_s = min(n - r, n - c);
				for (int s = max_s; s >= 1; --s) {
					if (r + s - 1 >= n || c + s - 1 >= n) continue;
					if (right[r][c] >= s && down[r][c] >= s &&
						right[r + s - 1][c] >= s && down[r][c + s - 1] >= s) {
						if (s > max_size || (s == max_size && (r < res_r || (r == res_r && c < res_c)))) {
							max_size = s;
							res_r = r;
							res_c = c;
						}
						break;
					}
				}
			}
		}
		
		return (max_size == 0) ? vector<int>() : vector<int>{res_r, res_c, max_size};
	}
};

// 法三
class Solution {
	public:
	vector<int> findSquare(vector<vector<int>>& matrix) {
		int n = matrix.size();
		if (n == 0) return {};

		// dp_row[i][j]: 从 (i, j) 开始向右有多少个连续的 0
		// dp_col[i][j]: 从 (i, j) 开始向下有多少个连续的 0
		vector<vector<int>> dp_row(n, vector<int>(n, 0));
		vector<vector<int>> dp_col(n, vector<int>(n, 0));
		int r = -1, c = -1, size = 0;

		// 填充 dp_row 和 dp_col
		for (int i = n - 1; i >= 0; i--) {
			for (int j = n - 1; j >= 0; j--) {
				if (matrix[i][j] == 0) {
					dp_row[i][j] = (j == n - 1) ? 1 : dp_row[i][j + 1] + 1;
					dp_col[i][j] = (i == n - 1) ? 1 : dp_col[i + 1][j] + 1;
				}
			}
		}

		// 寻找最大子方阵
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == 0) {
					int max_k = min(dp_row[i][j], dp_col[i][j]);
					for (int k = max_k; k >= 1; k--) {
						// 检查右下部分的边是否也满足条件
						if (dp_row[i + k - 1][j] >= k && dp_col[i][j + k - 1] >= k) {
							if (k > size) {
								size = k;
								r = i;
								c = j;
							}
							break; // 因为 k 是从大到小遍历的，找到最大后可以直接退出
						}
					}
				}
			}
		}

		if (size == 0) return {};
		return {r, c, size};
	}
};